package com.liang.bishi.other;

import java.util.Scanner;
import java.util.Stack;

/**
 * 中缀表达式计算
 * <p>
 * 使用 "双栈法" 来解决这个问题：一个栈用于存储操作数，另一个栈用于存储操作符。在处理表达式时，需要根据运算符的优先级来决定是否弹出操作符并计算当前的表达式
 * <p>
 * 3+5^2-9
 * 1
 */
public class Test1021 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String expression = in.next();
        System.out.println("计算结果: " + evaluateExpression(expression));
        in.close();
    }

    // 计算表达式的值：1+(4-2)*4/2
    public static int evaluateExpression(String expression) {
        Stack<Integer> operandStack = new Stack<>();  // 操作数栈
        Stack<Character> operatorStack = new Stack<>();  // 操作符栈
        int index = 0;

        while (index < expression.length()) {
            char ch = expression.charAt(index);
            if (Character.isDigit(ch)) {
                // 如果是数字，解析连续数字入栈
                int num = 0;
                while (index < expression.length() && Character.isDigit(expression.charAt(index))) {
                    num = num * 10 + (expression.charAt(index) - '0');
                    index++;
                }
                // 数字入栈
                operandStack.push(num);
                continue;
            } else if (ch == '(') {
                // 左括号直接入栈
                operatorStack.push(ch);
            } else if (ch == ')') {
                // 右括号弹出操作符进行计算，直到遇到左括号
                while (operatorStack.peek() != '(') {
                    processAnOperator(operandStack, operatorStack);
                }
                operatorStack.pop();
            } else if (isOperator(ch)) {
                // 遇到操作符，比较优先级并处理
                System.out.println(ch);
                while (!operatorStack.isEmpty() && precedence(operatorStack.peek()) >= precedence(ch)) {
                    processAnOperator(operandStack, operatorStack);
                }
                operatorStack.push(ch);  // 当前操作符入栈
            }
            index++;
        }
        // 处理剩余的操作符
        while (!operatorStack.isEmpty()) {
            processAnOperator(operandStack, operatorStack);
        }
        // 最终结果应该在操作数栈的顶部
        return operandStack.pop();
    }

    // 判断是否为操作符
    public static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
    }

    // 定义运算符的优先级
    public static int precedence(char operator) {
        switch (operator) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;  // 其他符号（如括号）优先级最低
    }

    // 执行一次操作符的计算
    public static void processAnOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        char operator = operatorStack.pop();
        int b = operandStack.pop();
        int a = operandStack.pop();
        operandStack.push(calculate(a, b, operator));  // 将计算结果压回操作数栈
    }

    // 根据操作符计算结果
    public static int calculate(int a, int b, char operator) {
        switch (operator) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return a / b;
            case '^':
                // return a ^ b;
                return (int) Math.pow(a, b);  // 处理幂运算
        }
        return 0;
    }

}
